#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto it:nums) sum+=it;
        if(sum%2!=0) return false;
        int n=nums.size();
        sum/=2;
        vector<vector<int>> dp(n+1,vector<int>(sum+1));
        for(int i=1;i<=sum;i++) dp[0][i]=-1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=sum;j++)
            {
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1]&&dp[i-1][j-nums[i-1]]!=-1)
                    dp[i][j]=max(dp[i][j],dp[i-1][j-nums[i-1]]);
                if(j==sum&&dp[i][j]!=-1) return true;
            }
        }
        return false;
    }
};